package com.sourcetrip.algorithm.sort.selection;

import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;

import java.util.Comparator;

/**
 * @author: ZhouBert
 * @date: 2020/12/29
 * @description: 十大排序算法之二：选择排序（的对象比较版本）
 */
public class SelectionCustomedSortV0<E> extends AbstractCustomedObjectSort<E> {

	public SelectionCustomedSortV0() {
	}

	public SelectionCustomedSortV0(E[] elements, Comparator<E> comparator) {
		super(elements, comparator);
	}

	public SelectionCustomedSortV0(E[] elements) {
		super(elements);
	}

	/**
	 * 可以看作在 bubble 上的优化：
	 * 因为全部比较完了才进行交换，而不是比较一次就交换一次
	 *
	 * @param objectArr
	 */
	@Override
	protected void sortArr(E[] objectArr) {
		//记录最大值的索引
		int index = 0;
		for (int end = objectArr.length - 1; end >= 0; end--) {
			for (int i = 1; i <= end; i++) {
				//等于时也进行交换！为了保持稳定性！
				if (compare(objectArr[index], objectArr[i]) <= 0) {
					index = i;
				}
			}
			//比较完一轮以后进行交换
			swap(index, end);
			//交换完毕后需要将 index 重置！
			index = 0;
		}
	}
}
